from collections import Counter
from math import ceil
import heapq


class Solution:
    def reorganizeString(self, S: str) -> str:
        counter = Counter(S)
        most = counter.most_common(1)
        if most[0][1] > ceil(len(S) / 2):
            return ""
        arr = []
        for key, value in counter.items():
            arr.append([-value, key])
        res = []
        heapq.heapify(arr)

        while len(arr) > 1:
            item1 = heapq.heappop(arr)
            item2 = heapq.heappop(arr)

            res.append(item1[1])
            res.append(item2[1])
            if item1[0] < -1:
                heapq.heappush(arr, [item1[0] + 1, item1[1]])

            if item2[0] < -1:
                heapq.heappush(arr, [item2[0] + 1, item2[1]])

        if arr:
            res.append(arr[0][1])

        return "".join(res)


if __name__ == "__main__":
    res = Solution().reorganizeString("bfrbs")
    print(res)
